Obeleži sve kategorije koje odgovaraju problemu

Модуларна аритметика

Кажемо да је број $r$ остатак при дељењу броја $x$ бројем $y$ и пишемо $x\,\mathrm{mod}\,y = r$ ако и само ако постоји број $q$ такав да је $x = q\cdot y + r$ и $0 \leq r < y$. Поред тога што са $\,\mathrm{mod}\,$ означавамо бинарну операцију, $\,\mathrm{mod}\,$ се може користити и као ознака бинарне релације у скупу целих бројева. Наиме, писаћемо $a\equiv b \,\mathrm{mod}\,m$ ако $m|(a-b)$. Ово је еквивалентно томе да $a$ и $b$ дају исти остатак при дељењу са $m$. На пример, пишемо $12\equiv 2 \,\mathrm{mod}\,5$ јер $5|(12-2)$.

Релацију $\,\mathrm{mod}\,$ користимо у неким свакодневним ситуацијама, а да тога често нисмо ни свесни.

• Један од таквих примера је рад са временом. Наиме, за 15 сати након 11 часова рећи ћемо да је 2 сата (што одговара томе да је $11+15 \equiv 2 \,\mathrm{mod}\,{24}$).

• Слично важи и за дане у недељи, које рачунамо по модулу 7. Ако је данас, рецимо, четвртак и интересује нас који ће дан бити за сто дана, не морамо да бројимо један по један дан. Сваком дану можемо придружити неки остатак при дељењу са 7 (0 - понедељак, 1 - уторак, 2 - среда, 3 - четвртак, 4 - петак, 5 - субота, 7 - недеља), а затим израчунати $(3 + 100) \,\mathrm{mod}\,7 = 5$ и знаћемо да је за 100 дана субота (проћи ће 14 пуних недеља тј. 98 дана и биће поново четвртак, након 99 дана ће бити петак, а након 100 субота). Аналогно се рачуна и месец или редни број недеље у години.

• Слично важи и приликом рада са угловима (које рачунамо по модулу 360 степени).

Модуларна аритметика има пуно практичних примена: користи се за израчунавање контролних сума за међународне стандардне идентификаторе књига (ISBN бројеве) и идентификаторе банки (IBAN). Модуларна аритметика је и у основи савремених криптографских система.

Бројеви се у рачунарима представљају по модулу $2^k$. На пример, у језику C++ бројеви типа unsigned int представљају се по модулу $2^{32}$. На пример, у језику C# бројеви типа uint представљају се по модулу $2^{32}$. У наредном коду резултат квадрирања броја $123456789$ биће вредност $123456789^2 \,\mathrm{mod}\,32 = 2537071545$.

unsigned int x = 123456789;
cout << x*x << endl;

Сабирање и множење по модулу

Уколико је потребно одредити вредност збира или производа бројева по модулу $m$ од помоћи нам могу бити наредне релације:

$$(a + b)\,\mathrm{mod}\,m = (a\,\mathrm{mod}\,m\ +\ b\,\mathrm{mod}\,m)\,\mathrm{mod}\,m$$

$$(a \cdot b)\,\mathrm{mod}\,m = (a\,\mathrm{mod}\,m\ \cdot\ b\,\mathrm{mod}\,m)\,\mathrm{mod}\,m$$

Одузимање по модулу

Размотримо проблем одређивања разлике бројева $b$ и $a$ по модулу $m$. На пример, потребно је одредити вредност $(b-a)\,\mathrm{mod}\,m$. Желели бисмо да као вредност овог израза добијемо ненегативну вредност чак и у случају када је $b < a$. Међутим, не постоји сагласност између различитих програмских језика у рачунању вредности x % m када је x негативно. Наиме, у језику C++ и у језику C# бисмо за вредност остатка добили негативан број: вредност израза (2 - 7) % 3 била би -2, док би у језику Python као резутат добили позитиван број 1. Уместо да вршимо испитивање да ли је дељеник негативан, ако је $0 \leq a, b < m$, позитиван резултат је могуће добити израчунавањем вредности израза $(b - a + m)\,\mathrm{mod}\,m$. Додавањем вредности $m$, вредност $b - a + m$ ће постати сигурно ненегативна (јер разлика $b-a$ не може бити мања од $-m$), а тражење остатка ће практично поништити првобитно додавање вредности $m$). У претходном смо се ослонили на чињеницу да су и $a$ и $b$ бројеви који су већи или једнаки од $0$ и строго мањи од $m$. Проналажење вредности разлике по модулу $m$ могуће је и у општем случају и важи

$$(B - A)\,\mathrm{mod}\,m = (B\,\mathrm{mod}\,m - A\,\mathrm{mod}\,m + m)\,\mathrm{mod}\,m$$

Степеновање по модулу

Као последица множења по модулу, важи и наредно тврђење, које омогућава да се израчуна степен по модулу:

$$a^n \,\mathrm{mod}\,m = (a\,\mathrm{mod}\,m)^n \,\mathrm{mod}\,m$$